package com.midea.leetcode;

import com.sun.deploy.util.StringUtils;

import java.util.ArrayList;
import java.util.List;

public class LeetCode93 {
    public static void main(String[] args) {
        String s= "19216801";
        //System.out.println(restoreIpAddresses(s));
        String xx = "00";
        boolean flag = Integer.parseInt(xx) == 0;
        System.out.println(flag);
    }
    public static List<String> restoreIpAddresses(String s) {
        List<String> result = new ArrayList<>();
        dfs(s,-1,1,new ArrayList<>(),result);
        return result;
    }
    public static void dfs(String ip, int index, int level,  List<String> res,List<String> result){
        //截止条件
        //Leetcode,不允许使用StringUtils工具类
        if (level == 5 || index == ip.length()-1){
            if (level == 5 && index == ip.length()-1){
                StringBuffer sb = new StringBuffer();
                for (int i = 0;i<res.size();i++){
                    if (i<res.size()-1){
                        sb.append(res.get(i));
                        sb.append(".");
                    }else{
                        sb.append(res.get(i));
                    }
                }
                result.add(sb.toString());
                //result.add(StringUtils.join(res,"."));
            }
            return;
        }
        //候选人，注意回溯
        for (int i = 1;i < 4;i++){
            if (index+i < ip.length()){
                String x = ip.substring(index+1,index+1+i);
                //每个坑位可以是0（只能有一位0），或者不以0开始
                //每个坑位必须小于256
                if (Integer.parseInt(x) < 256 && ((Integer.parseInt(x) == 0 && x.length() == 1) || !x.startsWith("0"))){
                    res.add(x);
                    dfs(ip,index+i,level+1,res,result);
                    res.remove(res.size()-1);
                }
            }
        }
    }
}
